#include<iostream>
#include<string>
using namespace std;
//模拟实现二叉搜索树k v 结构

namespace zyl
{



	template <class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _val;

		BSTreeNode(const K& key, const V& val)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _val(val)
		{}
	};

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:

		bool Insert(const K& key, const V& val)
		{
			//如果树为空，直接插入
			if (_root == nullptr)
			{
				_root = new Node(key, val);
				return true;
			}

			Node* cur = _root;//记录一下根节点
			Node* parent = nullptr;//定义父节点

			//寻找要插入的位置
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;//记录父节点
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;//记录父节点
					cur = cur->_left;
				}
				else
					return false;
			}
			//插入
			cur = new Node(key, val);
			if (key < parent->_key)
			{
				parent->_left = cur;
			}
			else if (parent->_key < key)
			{
				parent->_right = cur;
			}
			return true;
		}

Node* Find(const K& key)
{
		Node* cur = _root;//记录一下根节点
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key == key)
			{
				return cur;
			}
			}
		return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			//找key
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				//找到存放 key的节点 进行删除
				else
				{
					//key的左子树为空 所以父节点链接右子树
					if (cur->_left == nullptr)
					{
						//如果删除的是根节点，此时父节点指向为nullptr
						if (parent == nullptr)
						{
							//直接让_root指向下一个节点
							_root = _root->_right;
						}
						else
						{
							//判断应该链接到父节点的左还是右
							if (cur == parent->_left)
								parent->_left = cur->_right;
							else
								parent->_right = cur->_right;
						}
						delete cur;
					}
					//key的右子树为空 所以父节点链接左子树
					else if (cur->_right == nullptr)
					{
						//删除的为根节点的情况
						if (parent == nullptr)
						{
							_root = _root->_left;
						}
						else
						{
							//判断应当链接到父节点的左还是右
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
					}
					//删除节点左、右都不为空
					else
					{
						//指向cur，防止非法访问
						Node* minparent = cur;
						Node* min = cur->_right;
						while (min->_left != nullptr)
						{
							minparent = min;
							min = min->_left;
						}
						swap(cur->_key, min->_key);
						//解决野指针或min->right有子树的情况
						//minparent->_left = min->_right;
						//判断min在minparent的左或右
						if (minparent->_left == min)
							minparent->_left = min->_right;
						else
							minparent->_right = min->_right;
						delete min;
					}
					return true;
				}
			}
			return false;

		}


		void InOrder()//中序遍历调用接口
		{
			_InOrder(_root);
			cout << endl;
		}

	private:

		void _InOrder(Node* root)//中序遍历子函数
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_val << endl;;
			_InOrder(root->_right);
		}

		Node* _root = nullptr;
	};

}